/* Deterministic Algorithms
*
*
*/

#include "sudoku.h"

struct arg_t {
	Grid g;
	Grid gIn;
};

void *determine_pth(void *thread_data);

bool determine(Grid gIn,Grid g){

	int progress = 2;
	int x, y, s, num, mark;
	memcpy(g, gIn, sizeof(cell) * 81);
	
	while (progress > 1){
        	//printf("Determining....\n");
                progress = 1;
                s = 0;
                for (y = 0; y < GRID_SIZE; y++){
                        for (x = 0; x < GRID_SIZE; x++){
				num = bitCount(gridIndex(g,x,y));
                                if(num>1){
                                        //printf("Cell=%d:%d\n",x,y);
					//prtGrid(g,1);
					//prtGrid(g,2);
                                        s = onlyInColumn(g,x,y);
                                        if (s > 0){
                                                //printf("oIc Setting Cell (%d,%d) to %d\n",x,y,s);
                                                setCell(s, &gridIndex(g,x,y));
                                                progress = unmarkCellsint(g, x, y);
						if(progress < 1){
							//printf("CConfirm Error\n");
							//delGrid(g_guess);
							//delGrid(guess_out);
							return FALSE;
						}
						else{
							//printf("Update\n");
							//prtGrid(g,2);
                                                	break;
						}
                                        }
                                        s = onlyInRow(g,x,y);
                                        if (s > 0){
                                                setCell(s, &gridIndex(g,x,y));
                                                //printf("oIr Setting Cell (%d,%d) to %d\n",x,y,s);
                                                progress = unmarkCellsint(g, x, y);
						if(progress < 1){
							//printf("RConfirm Error\n");
							//delGrid(g_guess);
							//delGrid(guess_out);
							return FALSE;
						}
						else{
							//printf("Update\n");
							//prtGrid(g,2);
                                                	break;
						}
                                        }
                                        s = onlyInSquare(g,x,y);
                                        if(s > 0){
                                                setCell(s, &gridIndex(g,x,y));
						//printf("oIs Setting Cell (%d,%d) to %d\n",x,y,s);
                                                progress = unmarkCellsint(g, x, y);
						if(progress < 1){
							//printf("SConfirm Error\n");
							//delGrid(g_guess);
							//delGrid(guess_out);
							return FALSE;
						}
						else{
							//printf("Update\n");
							//prtGrid(g,2);
                                                	break;
						}
                                        }		
                                }
                        }
                        if(progress > 1){
                                break;
                        }
                }
        }

	cellCoord guess;
	int num_guess, i, j;
	cell test, gset;
	struct arg_t in[GRID_SIZE];
	pthread_t pthreads[GRID_SIZE];
	test = 0x1;
	j = 0;
	Grid g_guess[GRID_SIZE], guess_out[GRID_SIZE];
	prtGrid(g, 2);
	guess = getLeastPossCell(g);
	x = guess.x;
	y = guess.y;
	num_guess = bitCount(gridIndex(g,guess.x,guess.y));
	gset = 0x0;
	printf("(%d,%d) - num = %d\n",x,y,num_guess);
	j = 0;
	test = 0x1;
	printf("Guess Loop\n");
	for(i = 0; i<num_guess; i++){
		g_guess[i] = newGrid();
		guess_out[i] = newGrid();
		memcpy(g_guess[i], g, sizeof(cell) * 81);
		while(bitCount(gset) != 1){
			gset = test & gridIndex(g,x,y);
			j++;
			test = test << 1;
		}
		prtCell(gset,2);
		printf("Setting to %d\n",j);
		setCell(j,&gridIndex(g_guess[i],x,y));
		mark = unmarkCellsint(g_guess[i], x, y);
		prtGrid(g_guess[i],1);
		in[i].gIn = g_guess[i];
		in[i].g = guess_out[i];
		pthread_create(&pthreads[i], NULL, determine_pth,(void*) &in[i]); 
		gset = 0x0;
		j = 0;
	}

	for (i=0; i<num_guess; i++){
		pthread_join(pthreads[i], NULL);
	}
	
	for (i=0; i<num_guess; i++){
		if(isGridSolved(guess_out[i])){
			memcpy(g, guess_out, sizeof(cell) * 81);
		}		
	}

	return isGridSolved (g);
}

void* determine_pth(void *thread_data){

	struct arg_t *my_data;
	pthread_t pthreads[GRID_SIZE];

	my_data = (struct arg_t *) thread_data;

	Grid gIn = my_data->gIn;
	Grid g = my_data->g;

	int progress = 2;
	int x, y, s, num, mark;
	memcpy(g, gIn, sizeof(cell) * 81);
	
	while (progress > 1){
        	//printf("Determining....\n");
                progress = 1;
                s = 0;
                for (y = 0; y < GRID_SIZE; y++){
                        for (x = 0; x < GRID_SIZE; x++){
				num = bitCount(gridIndex(g,x,y));
                                if(num>1){
                                        //printf("Cell=%d:%d\n",x,y);
					//prtGrid(g,1);
					//prtGrid(g,2);
                                        s = onlyInColumn(g,x,y);
                                        if (s > 0){
                                                //printf("oIc Setting Cell (%d,%d) to %d\n",x,y,s);
                                                setCell(s, &gridIndex(g,x,y));
                                                progress = unmarkCellsint(g, x, y);
						if(progress < 1){
							//printf("CConfirm Error\n");
							//delGrid(g_guess);
							//delGrid(guess_out);
							pthread_exit(NULL);
						}
						else{
							//printf("Update\n");
							//prtGrid(g,2);
                                                	break;
						}
                                        }
                                        s = onlyInRow(g,x,y);
                                        if (s > 0){
                                                setCell(s, &gridIndex(g,x,y));
                                                //printf("oIr Setting Cell (%d,%d) to %d\n",x,y,s);
                                                progress = unmarkCellsint(g, x, y);
						if(progress < 1){
							//printf("RConfirm Error\n");
							//delGrid(g_guess);
							//delGrid(guess_out);
							pthread_exit(NULL);
						}
						else{
							//printf("Update\n");
							//prtGrid(g,2);
                                                	break;
						}
                                        }
                                        s = onlyInSquare(g,x,y);
                                        if(s > 0){
                                                setCell(s, &gridIndex(g,x,y));
						//printf("oIs Setting Cell (%d,%d) to %d\n",x,y,s);
                                                progress = unmarkCellsint(g, x, y);
						if(progress < 1){
							//printf("SConfirm Error\n");
							//delGrid(g_guess);
							//delGrid(guess_out);
							pthread_exit(NULL);
						}
						else{
							//printf("Update\n");
							//prtGrid(g,2);
                                                	break;
						}
                                        }		
                                }
                        }
                        if(progress > 1){
                                break;
                        }
                }
        }

	cellCoord guess;
	int num_guess, i, j;
	cell test, gset;
	struct arg_t in[GRID_SIZE];
	test = 0x1;
	j = 0;
	Grid g_guess[GRID_SIZE], guess_out[GRID_SIZE];

	guess = getLeastPossCell(g);
	x = guess.x;
	y = guess.y;
	num_guess = bitCount(gridIndex(g,guess.x,guess.y));
	if(x < 0 || y < 0){
		printf("Cell with Least Possibilities Error\n");
		return FALSE;
	} 
	gset = 0x0;
	j = 0;
	test = 0x1;
	//printf("Guess Loop\n");
	for(i = 0; i<num_guess; i++){
		g_guess[i] = newGrid();
		guess_out[i] = newGrid();
		memcpy(g_guess[i], g, sizeof(cell) * 81);
		while(bitCount(gset) != 1){
			gset = test & gridIndex(g,x,y);
			j++;
			test = test << 1;
		}
		setCell(j,&gridIndex(g_guess[i],x,y));
		mark = unmarkCellsint(g_guess[i], x, y);
		if(mark < 1){
			//printf("Immediate Bad Guess\n");
			//delGrid(g_guess);
			//delGrid(guess_out);
			pthread_exit(NULL);
		}
		in[i].gIn = g_guess[i];
		in[i].g = guess_out[i];
		pthread_create(&pthreads[i], NULL, determine_pth, (void*) &in[i]); 
		gset = 0x0;
	}

	for (i=0; i<num_guess; i++){
		pthread_join(pthreads[i], NULL);
	}

	for (i=0; i<num_guess; i++){
		prtGrid(guess_out[i],1);
		if(isGridSolved(guess_out[i])){
			memcpy(g, guess_out, sizeof(cell) * 81);
		}
		else pthread_exit(NULL);		
	}
}


int onlyInColumn(Grid g, int x, int y){
	
	cell mask = 0x1;
	cell test;
	int i, j, sum;
	//printf("Only Column Test\n");
	for(i = 1; i <= GRID_SIZE; i++){
		mask = mask << (i-1);
		test = mask & gridIndex(g,x,y);
		//printf("cell:");
		//prtCell(mask,0);
		//printf("\ntest:");
		//prtCell(test,0);
		//printf("\n");
		if(bitCount(test) == 1){
			//printf("Bit test passed\n");
			for (j = 0; j < GRID_SIZE; j++){
				if(j != y){
					test = mask & gridIndex(g,x,j);
					//printf("Column Test %d against %d, Result:",j,y);
					//prtCell(test,0);
					//printf("\n");
					sum = sum + bitCount(test);
				}
			}
			if(sum == 0){
				//printf("Column Check, Found Value\n");
				return i;
			}
		}
		sum = 0;
		mask = 0x1;
	}

	//printf("Column Check, Nothing Found\n");
	return 0;

}

int onlyInRow(Grid g, int x, int y){

	cell mask = 0x1;
	cell test;
	int i, j, sum;

	for(i = 1; i <= GRID_SIZE; i++){
		mask = mask << (i-1);
		test = mask & gridIndex(g,x,y);
		if(bitCount(test) == 1){
			for (j = 0; j < GRID_SIZE; j++){
				if(j != x){
					test = mask & gridIndex(g,j,y);
					sum = sum + bitCount(test);
				}
			}
			if(sum == 0){
				//printf("Row Check, Found Value\n");
				return i;
			}
		}
	sum = 0;
	mask = 0x1;
	}
	
	//printf("Row Check, Nothing Found\n");	
	return 0;

}

int onlyInSquare(Grid g, int x, int y){
	
	cell mask = 0x1;
	cell test;
	int sx, sy, sum, i, xi, yi;
	sx = getSubGridX(x);
	sy = getSubGridY(y);

	for(i = 1; i <= GRID_SIZE; i++){
		mask = mask << (i-1);
		test = mask & gridIndex(g,x,y);
		if(bitCount(test) == 1){
			for (yi = 0; yi < SUB_GRID_SIZE; yi++){
				for (xi = 0; xi < SUB_GRID_SIZE; xi++){
					if (&gridIndex(g, x, y) != &subGridIndex(g, sx, sy, xi, yi)){ // Diff Cells
						test = mask & subGridIndex(g, sx, sy, xi, yi);
						sum = sum + bitCount(test);
					}
				}
			}
			/*if(x == 5 && y == 6){
				prtCell(gridIndex(g, x, y), 2);
				printf(" Cell (6,7) Testing %d, Result:%d\n", i, sum);
			}*/
			if(sum == 0){
				//printf("Square Check, Found Value\n");
				return i;
			}
		}
	sum = 0;
	mask = 0x1;
	}

	//printf("Square Check, Nothing Found\n");
	return 0;
}

cell rowTuple(Grid g, int x, int y){

	cell mask = 0x1;
	cell result = 0x0;
	cell test;
	int m, i, j, sum;

	for(m = 0; m < GRID_SIZE; m += SUB_GRID_SIZE){	//Find Subgrid
		if(m <= x && x < (m + SUB_GRID_SIZE)){

			for(i = 1; i <= GRID_SIZE; i++){
				mask = mask << (i-1);
				test = mask & gridIndex(g,x,y);
				if(bitCount(test) == 1){
					for (j = 0; j < GRID_SIZE; j++){
						if(j < m || j >= m + SUB_GRID_SIZE){
							test = mask & gridIndex(g,j,y);
							sum = sum + bitCount(test);
						}
					}
					if(sum == 0){
						//printf("Row Tuple Check, Found Value\n");
						result |= mask;
					}
				}
			sum = 0;
			mask = 0x1;
			}

		}
	}
	//printf("Row Tuple Check, Nothing Found\n");
	return result;
}

cell columnTuple(Grid g, int x, int y){

	cell mask = 0x1;
	cell test;
	cell result = 0x0;
	int m, i, j, sum;
	//printf("Only Column Test\n");

	for(m = 0; m < GRID_SIZE; m += SUB_GRID_SIZE){	//Find Subgrid
		if(m <= y && y < (m + SUB_GRID_SIZE)){

			for(i = 1; i <= GRID_SIZE; i++){
				mask = mask << (i-1);
				test = mask & gridIndex(g,x,y);
				//printf("cell:");
				//prtCell(mask,0);
				//printf("\ntest:");
				//prtCell(test,0);
				//printf("\n");
				if(bitCount(test) == 1){
					//printf("Bit test passed\n");
					for (j = 0; j < GRID_SIZE; j++){
						if(j < m || j >= (m + SUB_GRID_SIZE)){
							test = mask & gridIndex(g,x,j);
							//printf("Column Test %d against %d, Result:",j,y);
							//prtCell(test,0);
							//printf("\n");
							sum = sum + bitCount(test);
						}
					}
					if(sum == 0){
						//printf("Column Check, Found Value\n");
						result |= mask;
					}
				}
				sum = 0;
				mask = 0x1;
			}
		}
	}


	//printf("Column Tuple Check, Nothing Found\n");
	return result;
}

cell squareColumnTuple(Grid g, int x, int y){

	cell mask = 0x1;
	cell test;
	cell result = 0x0;
	int sx, sy, sum, i, xi, yi, m, n;
	sx = getSubGridX(x);
	sy = getSubGridY(y);

	
	n = x+1;
	m = n%SUB_GRID_SIZE;	//Find Subgrid Column x value
	m++;

	for(i = 1; i <= GRID_SIZE; i++){
		mask = mask << (i-1);
		test = mask & gridIndex(g,x,y);
		if(bitCount(test) == 1){
			for (yi = 0; yi < SUB_GRID_SIZE; yi++){
				for (xi = 0; xi < SUB_GRID_SIZE; xi++){
					if (xi != (SUB_GRID_SIZE-m)){ // Avoid Test Cell Row
						test = mask & subGridIndex(g, sx, sy, xi, yi);
						sum = sum + bitCount(test);
					}
				}
			}
			/*if(x == 5 && y == 6){
				prtCell(gridIndex(g, x, y), 2);
				printf(" Cell (6,7) Testing %d, Result:%d\n", i, sum);
			}*/
			if(sum == 0){
				//printf("Square Check, Found Value\n");
				result |= mask;
			}
		}
	sum = 0;
	mask = 0x1;
	}
	
	//printf("Square Check, Nothing Found\n");
	return result;
}

cell squareRowTuple(Grid g, int x, int y){

	cell mask = 0x1;
	cell test;
	cell result = 0x0;
	int sx, sy, sum, i, xi, yi, m, n;
	sx = getSubGridX(x);
	sy = getSubGridY(y);

	n = y+1;
	m = n%SUB_GRID_SIZE;	//Find Subgrid Row y value
	m++;

	for(i = 1; i <= GRID_SIZE; i++){
		mask = mask << (i-1);
		test = mask & gridIndex(g,x,y);
		if(bitCount(test) == 1){
			for (yi = 0; yi < SUB_GRID_SIZE; yi++){
				for (xi = 0; xi < SUB_GRID_SIZE; xi++){
					if (yi != (SUB_GRID_SIZE-m)){ // Diff Cells
						test = mask & subGridIndex(g, sx, sy, xi, yi);
						sum = sum + bitCount(test);
					}
				}
			}
			/*if(x == 5 && y == 6){
				prtCell(gridIndex(g, x, y), 2);
				printf(" Cell (6,7) Testing %d, Result:%d\n", i, sum);
			}*/
			if(sum == 0){
				//printf("Square Check, Found Value\n");
				result |= mask;
			}
		}
	sum = 0;
	mask = 0x1;
	}
	
	//printf("Square Check, Nothing Found\n");
	return result;
}

